package com.cet.programmercarl.algorithmperformancanalysis.双指针法;

/**
 * @program: algorithm
 * @description: 反转链表
 * @author: 陈恩涛
 * @create: 2022-03-24 17:24
 **/
public class ReverseLinkedList {

    /**
     * 双指针法
     * @param head
     * @return
     */
    private ListNode reverseList(ListNode head) {
        ListNode left = null;
        ListNode right = head;
        while (right != null) {
            ListNode temp = right.next;
            right.next = left;
            left = right;
            right = temp;
        }
        return left;
    }

    /**
     * 递归法
     * @param head
     * @return
     */
    private ListNode reverseList2(ListNode head) {
        return reverseList(null, head);
    }

    private ListNode reverseList(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;
        cur.next = prev;
//        prev = cur;
//        cur = temp;
        return reverseList(cur, temp);
    }

    public static void main(String[] args) {
        ListNode listNode = ListNode.init(1, 2, 3, 4, 5);
        System.out.println(listNode.toString());
        System.out.println(new ReverseLinkedList().reverseList(listNode).toString());
    }
}
